package interview.algorithms;

import common.ListNode;
import common.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 2018/8/6 10:10
 */
public class LeetTop200 {
    /**
     * 3. Longest Substring Without Repeating Characters
     * bf   2.Sliding Window
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans,j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

    /**
     * 4. Median of Two Sorted Arrays
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        int[] nums = new int[n];
        int index = 0;
        for (int i = 0; i < nums1.length; i++) {
            nums[index++] = nums1[i];
        }
        for (int i = 0; i < nums2.length; i++) {
            nums[index++] = nums2[i];
        }
        Arrays.sort(nums);
        if (n % 2 == 0) {
            return (nums[n / 2 - 1] + nums[n / 2]) / 2.0;
        } else {
            return nums[n / 2];
        }
    }
    static int[] tmp;
    void mergeSort(int[] a, int n) {
        tmp = new int[n];
        mergeSort(a, 0, n - 1);
    }
    void merge(int[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            tmp[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
           if (i > mid) {
               a[k] = tmp[j++];
           } else if (j > hi) {
               a[k] = tmp[i++];
           } else if (a[i] < a[j]) {
               a[k] = tmp[i++];
           } else {
               a[k] = tmp[j++];
           }
        }
    }
    void mergeSort(int[] a, int lo, int hi) {
        if (hi <= lo){
        return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    /**
     * 10. Regular Expression Matching
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) {
            return text.isEmpty();
        }
        boolean first_match = (!text.isEmpty() &&
                (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
        if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
            return isMatch(text,pattern.substring(2)) ||
                    (first_match && isMatch(text.substring(1),pattern));
        } else {
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }

    public boolean isMatchI(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        boolean first_match = (!s.isEmpty() &&
                (p.charAt(0) == s.charAt(0) || p.charAt(0) =='?'));
        if (p.length() >= 2 && p.charAt(1) == '*') {
            return isMatchI(s,p.substring(2)) ||
                    (first_match && isMatchI(s.substring(1),p));
        } else {
            return first_match && isMatchI(s.substring(1),p.substring(1));
        }
    }

    /**
     * 11. Container With Most Water
     * 1.bf 2.double i j
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int res = 0;
        while (i < j) {
            res = Math.max(res,Math.min(height[i],height[j]) * (j - i));
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return res;
    }

    /**
     * 14. Longest Common Prefix
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String res = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(res)) {
                res = res.substring(0,res.length() - 1);
            }
        }
        return res;
    }

    /**
     * 15. 3Sum
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            int target = -nums[i];

            while (j < k) {
                if (nums[j] + nums[k] == target) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[j]);
                    tmp.add(nums[k]);

                    j++;
                    k--;
                    res.add(tmp);
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                } else if (nums[j] + nums[k] < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return res;
    }
    private static final String[] KEYS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    public List<String> letterCombinations(String digits) {
        List<String> ret = new LinkedList<String>();
        combination("", digits, 0, ret);
        return ret;
    }
    private void combination(String prefix, String digits, int offset, List<String> ret) {
        if (offset >= digits.length()) {
            ret.add(prefix);
            return;
        }
        String letters = KEYS[(digits.charAt(offset) - '0')];
        for (int i = 0; i < letters.length(); i++) {
            combination(prefix + letters.charAt(i),digits,offset + 1,ret);
        }
    }



    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n < 1) {
            return head;
        }
        ListNode cur = head;
        // 每走一步,k-- 到末尾  k = k - n;
        while (cur != null) {
            n--;
            cur = cur.next;
        }
        if (n == 0) {
            head = head.next;
        }
        // ++k 到0 时停止,  此时停在n - k 位置.即要删除的节点前一个节点
        if (n < 0) {
            cur = head;
            while (++n != 0) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return head;
    }

    /**
     * 23. Merge k Sorted Lists
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> list = new ArrayList<>();
        for (ListNode listNode : lists) {
            while (listNode != null) {
                list.add(listNode.val);
                listNode = listNode.next;
            }
        }
        Collections.sort(list);
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        for (Integer val: list
             ) {
            cur.next = new ListNode(val);
            cur = cur.next;
        }
        return head.next;

    }

    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
               if (height[left] >= left_max) {
                   left_max = height[left];
               } else {
                   ans += left_max - height[left];
               }
               left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    ans += right_max - height[right];
                }
                right--;
            }
        }
        return ans;
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backTrackingForPermute(nums,new ArrayList<>(),res);
        return res;
    }
    private void backTrackingForPermute(int[] nums,List<Integer> tmpList,List<List<Integer>> res) {
        if (tmpList.size() == nums.length) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tmpList.contains(nums[i])) {
                    continue;
                }
                tmpList.add(nums[i]);
                backTrackingForPermute(nums,tmpList,res);
                tmpList.remove(tmpList.size() - 1);
            }
        }
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        if (strs == null || strs.length == 0){
            return res;
        }
        Map<String, List<String>> ans = new HashMap<>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = String.valueOf(ca);
            if (!ans.containsKey(key)) {
                ans.put(key, new ArrayList());
            }
            ans.get(key).add(s);
        }
        return new ArrayList<>(ans.values());
    }

    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        boolean neg = false;
        if (n < 0) {
            n = -n;
            neg = true;
        }
        double half = myPow(x,n >> 1);
        double ret = 0;
        if (n % 2 == 1) {
            ret = half * half * x;
        } else {
            ret = half * half;
        }
        return neg ? 1 / ret : ret;
    }

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int max = nums[0];
        int cur = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (cur < 0) {
                cur = 0;
            }
            cur += nums[i];
            max = Math.max(cur,max);
        }
        return max;
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length < 1) {
            return res;
        }
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            spiralOrderCore(matrix,tR++,tC++,dR--,dC--,res);
        }
        return res;
    }
    private void spiralOrderCore(int [][] matrix, int tR, int tC, int dR, int dC,List<Integer> res) {
        if (tR == dR) {
            for (int i = tC; i <= dC; i++) {
                res.add(matrix[tR][i]);
            }
        } else if (tC == dC) {
            for (int i = tR; i <= dR; i++) {
                res.add(matrix[i][tC]);
            }
        } else {
            int curC = tC;
            int curR = tR;
            while (curC != dC) {
                res.add(matrix[curR][curC]);
                curC++;
            }
            while (curR != dR) {
                res.add(matrix[curR][curC]);
                curR++;
            }
            while (curC != tC) {
                res.add(matrix[curR][curC]);
                curC--;
            }
            while (curR != tR) {
                res.add(matrix[curR][curC]);
                curR--;
            }
        }

    }


    public boolean canJump(int[] nums) {
        if (nums == null || nums.length < 1) {
            return false;
        }
        int cur = 0;
        int next = 0;
        for (int i = 0; i < nums.length; i++) {
            if (cur < i) {
                cur = next;
                if (next < i) {
                    return false;
                }
            }
            next = Math.max(next,i + nums[i]);

        }
        return next >= nums.length - 1;
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backTrackingForSubSet(res,nums,0,new ArrayList<>());
        return res;
    }
    public void  backTrackingForSubSet(List<List<Integer>> res,int[] nums,int index,List<Integer> tmpList) {
        res.add(new ArrayList<>(tmpList));
        for (int i = index; i < nums.length; i++) {
            tmpList.add(nums[i]);
            backTrackingForSubSet(res,nums,i + 1,tmpList);
            tmpList.remove(tmpList.size() - 1);
        }
    }

    public boolean exist(char[][] board, String word) {
        if (board == null && word == null) {
            return true;
        }
        int r = board.length;
        int c = board[0].length;
        boolean[][] used = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (dfs(board,word,i,j,used,0)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board,String word,int curR,int curC,boolean[][] used,int index) {
        if (index == word.length()) {
            return true;
        }
        if (curR >= board.length || curR < 0 || curC >= board[0].length || curC < 0) {
            return false;
        }
        if (used[curR][curC]) {
            return false;
        }
        if (board[curR][curC] != word.charAt(index)) {
            return false;
        }
        used[curR][curC] = true;
        if (dfs(board,word,curR + 1,curC,used,index + 1) ||
                dfs(board,word,curR - 1, curC,used,index + 1) ||
                dfs(board,word,curR, curC + 1,used,index + 1) ||
                dfs(board,word,curR, curC - 1,used,index + 1)) {
            return true;
        }
        used[curR][curC] = false;
        return false;
    }
    public int numDecodings(String s) {
        if(s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        for (int i = 2; i <= n; i++) {
            int first = Integer.valueOf(s.substring(i-1, i));
            int second = Integer.valueOf(s.substring(i-2, i));
            if (first >= 1 && first <= 9) {
                dp[i] += dp[i - 1];
            }
            if (second >= 10 && second <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode cur = stack.pop();
                res.add(cur.val);
                root = cur.right;
            }
        }
        return res;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length < 1) {
            return null;
        }
        return buildTree(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
    }
    public TreeNode buildTree(int[] preorder, int ps,int pe,int[] inorder,int is,int ie) {
        if (ps > pe || pe >= preorder.length || is > ie || ie >= inorder.length) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[ps]);
        int rootIndex = 0;
        for (int i = is; i <= ie; i++) {
            if (root.val == inorder[i]) {
                rootIndex = i;
                break;
            }
        }
        int leftLen = rootIndex - is;
        root.left = buildTree(preorder,ps + 1,ps +  leftLen,inorder,is,rootIndex - 1);
        root.right = buildTree(preorder,ps + leftLen + 1,pe,inorder,rootIndex + 1,ie);
        return root;
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        // First base case; if user requests zero rows, they get zero rows.
        if (numRows == 0) {
            return triangle;
        }
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int i = 1; i < numRows; i++) {
            List<Integer> cur = new ArrayList<>();
            List<Integer> pre = triangle.get(i - 1);

            cur.add(1);
            for (int j = 1; j < i; j++) {
               cur.add(pre.get(j - 1) + pre.get(j));
            }
            cur.add(1);

            triangle.add(cur);
        }
        return triangle;
    }
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSumCore(root);
        return max;
    }
    public int maxPathSumCore(TreeNode root) {
        if (root == null) {
            return 0;
        }

       int left = Math.max(0,maxPathSum(root.left));
        int  right =Math.max(0, maxPathSum(root.right));
        max = Math.max(max,left + right + root.val);
        return  Math.max(left, right) + root.val;
    }

    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;
        for (int num : nums) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (num_set.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                longestStreak = Math.max(longestStreak,currentStreak);
            }
        }
        return longestStreak;
    }

    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null) {
            return res;
        }
        backTrackingForPartition(res,s,new ArrayList<>(),0);
        return res;
    }
    private void backTrackingForPartition(List<List<String>> res,
                                          String s,
                                          List<String> tmpList,
                                          int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = start; i < s.length(); i++) {
                if (isPalindrome(s,start,i)) {
                    tmpList.add(s.substring(start,i + 1));
                    backTrackingForPartition(res,s,tmpList,i + 1);
                    tmpList.remove(tmpList.size() - 1);
                }
            }
        }
    }
    public  boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo++) != s.charAt(hi--)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 130. Surrounded Regions
     * @param board
     */
    public void solve(char[][] board) {
        if (board.length < 2 || board[0].length < 2) {
            return;
        }
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                boundaryDFS(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                boundaryDFS(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                boundaryDFS(board, 0, j);
            }
            if (board[m-1][j] == 'O') {
                boundaryDFS(board, m - 1, j);
            }
        }
        //post-prcessing, turn 'O' to 'X', '*' back to 'O', keep 'X' intact.
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '*') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    //Use DFS algo to turn internal however boundary-connected 'O' to '*';
    private void boundaryDFS(char[][] board, int i, int j) {
        if (i < 0 || i > board.length - 1 || j <0 || j > board[0].length - 1) {
            return;
        }
        if (board[i][j] == 'O') {
            board[i][j] = '*';
        }

        if (i > 1 && board[i - 1][j] == 'O') {
            boundaryDFS(board, i-1, j);
        }
        if (i < board.length - 2 && board[i+1][j] == 'O') {
            boundaryDFS(board, i + 1, j);
        }
        if (j > 1 && board[i][j-1] == 'O') {
            boundaryDFS(board, i, j - 1);
        }
        if (j < board[i].length - 2 && board[i][j+1] == 'O' ) {
            boundaryDFS(board, i, j + 1);
        }
    }
        // 保持一个pre 中序比较
    public boolean isValidBST(TreeNode root) {
        return true;
    }

// -------------------------- bad code -------------------
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length < 1) {
            return 0;
        }
        int lo = 0;
        int hi = heights.length - 1;
        int max = heights[0];
        while (lo < hi) {
            max = Math.max(findMin(heights,lo,hi) * (hi - lo + 1),max);
            if (heights[lo] < heights[hi]) {
                lo++;
            } else {
                hi--;
            }
        }
        return max;
    }
    private int findMin(int[] a,int i,int j) {
        int min = a[i];
        for (int k = i + 1; k <= j; k++) {
            min = Math.min(min,a[k]);
        }
        return min;
    }

    public String minWindow(String s, String t) {
        String res = "";
        if (s == null || t == null) {
            return res;
        }
        char[] ts = t.toCharArray();
        Arrays.sort(ts);
        int minLen = s.length();
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String cur = s.substring(i,j);
                char[] curs = cur.toCharArray();
                Arrays.sort(curs);
                if (String.valueOf(curs).contains(String.valueOf(ts))) {
                    if (curs.length <= minLen) {
                        res = cur;
                        minLen = curs.length;
                    }
                }
            }
        }
        return res;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] f = new boolean[s.length() + 1];
        f[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (f[j] && wordDict.contains(s.substring(j,i))) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[s.length()];
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // step 1. cut the list to two halves
        ListNode prev = null, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        // step 2. sort each half
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);

        // step 3. merge l1 and l2
        return merge(l1, l2);

    }
    ListNode merge(ListNode l1, ListNode l2) {
        ListNode l = new ListNode(0), p = l;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        if (l1 != null) {
            p.next = l1;
        }

        if (l2 != null) {
            p.next = l2;
        }

        return l.next;

    }
    int maxProduct(int A[], int n) {
        // store the result that is the max we have found so far
        int res = A[0];
        int max = res;
        int min = res;
        for (int i = 1; i < n; i++) {
            if (A[i] < 0) {
                int tmp = max;
                max= min;
                min = tmp;
            }
            max = Math.max(A[i],max * A[i]);
            min = Math.min(A[i],min * A[i]);
            res = Math.max(res,max);
        }
        return res;
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }

    public String largestNumber(int[] nums) {
        String[] s = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            s[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(s, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });
        if (s[0].equals("0")) {
            return "0";
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length; i++) {
            stringBuilder.append(s[i]);
        }
        return stringBuilder.toString();
    }


    @Test
    public void test() {
        int[] n = {3,30,34,5,9};
        System.out.println(largestNumber(n));
//        System.out.println(minWindow("ADOBECODEBANC","ABC"));
    }
}

class MinStack {
    private LinkedList<Integer> stack;
    private LinkedList<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new LinkedList<>();
        min = new LinkedList<>();
    }

    public void push(int x) {
        stack.push(x);
        if (min == null) {
            min.push(x);
        } else if (x <= getMin()) {
            min.push(x);
        }
    }

    public int pop() {
        int pop = stack.pop();
        if (pop == getMin()) {
            min.pop();
        }
        return pop;
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min.peek();
    }
}

class Node {
    int key;
    int value;
    Node pre;
    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }

}
class LRUCache {
    HashMap<Integer, Node> map;
    int capicity, count;
    Node head, tail;
    public LRUCache(int capacity) {
        this.capicity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
        head.pre = null;
        tail.next = null;
        count = 0;
    }
    public void deleteNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    public void addToHead(Node node) {
        node.next = head.next;
        node.next.pre = node;
        node.pre = head;
        head.next = node;
    }
    public int get(int key) {
        if (map.get(key) != null) {
            Node node = map.get(key);
            int result = node.value;
            deleteNode(node);
            addToHead(node);
            return result;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.get(key) != null) {
            Node node = map.get(key);
            node.value = value;
            deleteNode(node);
            addToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            if (count < capicity) {
                count++;
                addToHead(node);
            } else {
                map.remove(tail.pre.key);
                deleteNode(tail.pre);
                addToHead(node);
            }
        }
    }
}
